﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class Solution122
{
    //和买卖股票一的区别是可以多次买卖
    //所以在谷底买入，在谷峰卖出
    //这个想法是正确的，谷峰减去谷底，等于把所有的上坡加起来
    public int MaxProfit2(int[] prices)
    {
   
        int maxProfit=0;//低价买入

        int pre = 0;
        int cur = 0;
        int buy = 0;
        int sell = 0;
       bool have=false;

        for (int i = 1; i < prices.Length; i++) {

           cur= prices[i+1]- prices[i];
            if (pre >= 0 && cur < 0)//峰值，卖出
            {
                if (have)//持有就卖出
                {
                    maxProfit += prices[i];
                    have=! have;
                }

            }
            if (pre <= 0 && cur > 0)//谷值，卖入
            {
                if (!have)//持有就卖出
                {
                    maxProfit -= prices[i];
                    have = !have;
                }
            }


         pre = cur;
        }
       
        return maxProfit;
    }
    public int MaxProfit(int[] prices)//动态规划
    {

        //每天有两种选择，持有不持有
        int[][] dp= new int[prices.Length][];
        for (int i = 0;i< prices.Length; i++)
        {

            dp[i] = new int[2];

        }

        //第一天有股票
        dp[0][1] = -prices[0];
        //第一天没有股票
        dp[0][0] = 0;


        for (int i = 1; i < prices.Length; i++)
        {

            //今天持有，1，昨天没有，今天买入  2，昨天持有
          dp[i][1] =Math.Max( dp[i-1][0]-prices[i], dp[i-1][1]);
            //今天不持有，1，昨天不持有  2，昨天持有，今天卖出
            dp[i][0] = Math.Max(dp[i - 1][1] + prices[i], dp[i - 1][0]);


        }

        return dp[prices.Length-1][0];//最后一天手里一定不能有股票
    }
    public int MaxProfit3(int[] prices)//观察规律
    {

        int maxProfit = 0;//低价买入



        for (int i = 1; i < prices.Length; i++)
        {

            int cur = prices[i + 1] - prices[i];

            if (cur > 0)//谷值，卖入
            {
                maxProfit += cur;
            }



        }

        return maxProfit;
    }
}
class Program122
{

    static void Main122()
    {
        Solution121 solution = new Solution121();
        int[] prices = { 7, 1, 5, 3, 6, 4 };
        int maxProfit = solution.MaxProfit(prices);
        Console.WriteLine("Max Profit: " + maxProfit);
        Console.ReadKey();

    }
}
